import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Factorial {

    public static byte[][] MULTIPLY = {
        {
            0, 0, 0, 0, 0, 0, 0, 0, 0, 0
        }, {
            0, 1, 2, 3, 4, 5, 6, 7, 8, 9
        }, {
            0, 2, 4, 6, 8, 10, 12, 14, 16, 18
        }, {
            0, 3, 6, 9, 12, 15, 18, 21, 24, 27
        }, {
            0, 4, 8, 12, 16, 20, 24, 28, 32, 36
        }, {
            0, 5, 10, 15, 20, 25, 30, 35, 40, 45
        }, {
            0, 6, 12, 18, 24, 30, 36, 42, 48, 54
        }, {
            0, 7, 14, 21, 28, 35, 42, 49, 56, 63
        }, {
            0, 8, 16, 24, 32, 40, 48, 56, 64, 72
        }, {
            0, 9, 18, 27, 36, 45, 54, 63, 72, 81
        }
    };

    public static byte[][] PLUS = {
        {
            0, 1, 2, 3, 4, 5, 6, 7, 8, 9
        }, {
            1, 2, 3, 4, 5, 6, 7, 8, 9, 10
        }, {
            2, 3, 4, 5, 6, 7, 8, 9, 10, 11
        }, {
            3, 4, 5, 6, 7, 8, 9, 10, 11, 12
        }, {
            4, 5, 6, 7, 8, 9, 10, 11, 12, 13
        }, {
            5, 6, 7, 8, 9, 10, 11, 12, 13, 14
        }, {
            6, 7, 8, 9, 10, 11, 12, 13, 14, 15
        }, {
            7, 8, 9, 10, 11, 12, 13, 14, 15, 16
        }, {
            8, 9, 10, 11, 12, 13, 14, 15, 16, 17
        }, {
            9, 10, 11, 12, 13, 14, 15, 16, 17, 18
        }
    };

    /**
     * @param args
     */
    public static void main(String[] args) {

        long start = System.currentTimeMillis();
        //int n = 100000;
        int n = 10000;
        //int len = (int) (((1.0 / 2.0 * Math.log(2 * 3.1416) + n * Math.log(n) - n) / Math.log(10)) + Math.log10(n)) + 1;
        //byte[] factorial = new byte[len];
        //Arrays.fill(factorial, (byte) 0);
        //System.out.println(len);

        byte[] bResult = {
            1
        };

        for (int i = 2; i <= n; i++) {
            bResult = multiply(bResult, Integer.toString(i));
        }

        System.out.println("\nrun time: " + (System.currentTimeMillis() - start) + "ms");

        start = System.currentTimeMillis();

        int end = bResult.length - 1;
        while (bResult[end] == 0)
            end--;

        for (int i = end; i >= 0; i--) {
            //System.out.print(bResult[i]);
        }

        System.out.println("\nshow time: " + (System.currentTimeMillis() - start) + "ms");
    }

    public static byte[] multiply(byte[] num1, String str) {

        byte[] num2 = str.getBytes();

        for (int i = 0; i < num2.length; i++)
            num2[i] = (byte) (num2[i] - '0');
        byte swap;
        for (int i = 0, j = num2.length - 1; i < j; i++, j--) {
            swap = num2[i];
            num2[i] = num2[j];
            num2[j] = swap;
        }

        return multiply(num1, num2);
    }

    public static byte[] multiply(byte[] num1, byte[] num2) {

        Map<Byte, byte[]> mapResult = new HashMap<Byte, byte[]>();

        byte[] result = new byte[num1.length + num2.length];

        for (int i = 0; i < num2.length; i++) {
            if (num2[i] == 0)
                continue;
            byte[] multiplyTemp = mapResult.get(num2[i]);
            if (multiplyTemp == null) {
                multiplyTemp = multiply(num1, num2[i]);
                mapResult.put(num2[i], multiplyTemp);
            }

            plus(result, multiplyTemp, i);

        }
        return result;

    }

    public static byte[] multiply(byte[] num1, byte digit) {

        int end = num1.length - 1;
        while (num1[end] == 0)
            end--;

        byte[] result = Arrays.copyOfRange(num1, 0, end + 2);

        byte up = 0;
        for (int i = 0; i < end + 1; i++) {
            byte bMultiply = MULTIPLY[result[i]][digit];
            byte bPlus = PLUS[bMultiply % 10][up];
            result[i] = (byte) (bPlus % 10);
            up = PLUS[bPlus / 10][bMultiply / 10];
        }

        if (up != 0) {
            result[end + 1] = up;
            return result;
        }

        end = result.length;
        while (end > 0 && result[end - 1] == 0)
            end--;
        return Arrays.copyOfRange(result, 0, end);
    }

    public static void plus(byte[] num1, byte[] num2, int offset) {

        byte up = 0;
        byte b = 0;
        byte bPlus = 0;
        for (int i = 0; i < num1.length - offset; i++) {
            b = i < num2.length ? num2[i] : 0;

            b = PLUS[num1[i + offset]][b];

            bPlus = PLUS[b % 10][up];
            num1[i + offset] = (byte) (bPlus % 10);
            up = PLUS[bPlus / 10][b / 10];

        }

    }
}
